#include "main/utils.h"
using namespace std;

int lengthOfLongestSubString1(const string &str) {
  map<char, int> help_map;
  int max_len = 0;
  int cur_len = 0;
  int begin = 0;
  for (int i = 0; i < str.length(); ++i) {
    if (help_map.find(str[i]) == help_map.end()) {
      help_map[str[i]] = i;
      ++cur_len;
    } else {
      auto pre_idx = help_map[str[i]];
      if (pre_idx < i - cur_len) {
        ++cur_len;
      } else {
        begin = help_map[str[i]] + 1;
        cur_len = i - begin + 1;
      }
      help_map[str[i]] = i;
    }
    if (cur_len > max_len) {
      max_len = cur_len;
    }
  }
  return max_len;
}

int lengthOfLongestSubString11(const string &str) {
  int max_len = 0;
  int begin = 0;
  int repeat = 0;
  map<char, int> help_map;
  for (int end = 0; end < str.size(); ++end) {
    if (help_map.find(str[end]) == help_map.end()) {
      help_map[str[end]] = 1;
      auto cur_len = end - begin + 1;
      if (cur_len > max_len) {
        max_len = cur_len;
      }
    } else {
      ++help_map[str[end]];
      if (help_map[str[end]] > 1) {
        ++repeat;
      }
    }
    while (repeat != 0) {
      --help_map[str[begin]];
      if (help_map[str[begin]] == 1) {
        --repeat;
      }
      ++begin;
    }
  }
  return max_len;
}

int main() {
  string str = "babcca";
  int ret = lengthOfLongestSubString1(str);
  int ret1 = lengthOfLongestSubString11(str);
  cout << ret << " " << ret1 << endl;

  ret = lengthOfLongestSubString1("abcacfrar");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 4" << endl;

  ret = lengthOfLongestSubString1("acfrarabc");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 4" << endl;

  ret = lengthOfLongestSubString1("arabcacfr");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 4" << endl;

  ret = lengthOfLongestSubString1("aaaa");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 1" << endl;

  ret = lengthOfLongestSubString1("abcdefg");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 7" << endl;

  ret = lengthOfLongestSubString1("aaabbbccc");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 2" << endl;

  ret = lengthOfLongestSubString1("abcdcba");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 4" << endl;

  ret = lengthOfLongestSubString1("abcdaef");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 6" << endl;

  ret = lengthOfLongestSubString1("a");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 1" << endl;

  ret = lengthOfLongestSubString1("");
  cout << "The longest sub string without duplicate character: " << ret << " expected: 0" << endl;

  return 0;
}
